package Hot100.leetcode.editor.cn.code.子串;

import java.util.HashMap;

//Java：和为 K 的子数组
public class SubarraySumEqualsK{
    public static void main(String[] args) {
        Solution solution = new SubarraySumEqualsK().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    //
    //假设 nums = [1, 2, 3]，k = 3
    //初始化：
    //prefixSumCount = {0: 1}
    //count = 0
    //prefixSum = 0
    //处理第一个元素 1：
    //prefixSum = 0 + 1 = 1
    //查找 prefixSum - k = 1 - 3 = -2，不存在
    //更新 prefixSumCount = {0: 1, 1: 1}
    //处理第二个元素 2：
    //prefixSum = 1 + 2 = 3
    //查找 prefixSum - k = 3 - 3 = 0，存在且次数为 1
    //count = 0 + 1 = 1（子数组[1,2]的和为3）
    //更新 prefixSumCount = {0: 1, 1: 1, 3: 1}
    //处理第三个元素 3：
    //prefixSum = 3 + 3 = 6
    //查找 prefixSum - k = 6 - 3 = 3，存在且次数为 1
    //count = 1 + 1 = 2（子数组[3]的和为3）
    //更新 prefixSumCount = {0: 1, 1: 1, 3: 1, 6: 1}
    //返回 count = 2


class Solution {
        public int subarraySum(int[] nums, int k) {
            HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
            //初始化，前缀和为0出现次数为1
            prefixSumCount.put(0,1);
            //结果计数
            int count = 0;
            //遍历数组当前的前缀和
            int prefixSum = 0;

            for (int num : nums) {
                //1，先更新当前前缀和
                prefixSum += num;
                //2.判断 核心思想当前前缀和 - 前一个前缀和 = k那么就有子数组和为k
                //前一个和 = 当前 -k 因为我们现在获取的就是当前的对比之前的看是否存在 value即使存在的次数不断更新
                if(prefixSumCount.containsKey(prefixSum - k)){
                    count += prefixSumCount.get(prefixSum -k); //value 次数
                }

                //3.还需要更新注意是当前的前缀和出现的这个次数，，value这个次数 你不更新后面的怎么找你？
                //getOrDefault方法  可能会出现0导致前缀和相同那么0就可以搭配出可能所以不能忽略
                prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0)+1);

            }
            return  count;


        }
//leetcode submit region end(Prohibit modification and deletion)

    }
}